import javax.swing.tree.TreeNode;

public class Solution {
    class  TreeNode{
       public char val;
       public TreeNode left;
       public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }
    // 判断两棵树是否相等
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 当其中之一有一个空时，不相等
        if(p==null&&q!=null||p!=null&&q==null)
            return false;
        // 当两个都为空时，是相等的
        if(p==null&&q==null)
            return true;
        // 接下来的一定两个都不为空,判断值是否相等
        if(p.val!= q.val)
            return false;
        // 早判断左右树的值
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);

    }
    // 判断一棵树是否是一棵树的子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null)
            return false;
        if(isSameTree(root,subRoot))
            return true;
        if(isSameTree(root.left,subRoot))
            return true;
        if (isSameTree(root.right,subRoot))
            return true;
        return false;

    }
    // 翻转二叉树
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return null;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
    // 求一棵树的高度
    public int getHeight(TreeNode root){
        if(root == null)
            return 0;
        int leftH = getHeight(root.left);
        int rightH= getHeight(root.right);
        return (leftH>rightH?leftH:rightH)+1;
    }
    // 判断一棵树是否为平衡树（一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 ）
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        // 先判断 root 的左右高度是否超过1,再判断 root 的左右子树
        int leftH = getHeight(root.left);
        int right = getHeight(root.right);
        return Math.abs(leftH-right)<2
                &&isBalanced(root.left)
                &&isBalanced(root.right);
    }
    // 判断一棵树是否为平衡树
    // 方法二：
    public boolean isBalanced2(TreeNode root){
        if(root == null){
            return true;
        }
        return getHeight2(root)>=0;

    }
    // 求一棵树的高度
    public int getHeight2(TreeNode root){
        if(root == null)
            return 0;
        int leftH = getHeight2(root.left);
        int rightH= getHeight2(root.right);
        if(leftH>=0&&rightH>=0&&Math.abs(leftH-rightH)<=1){
            return Math.max(leftH,rightH)+1;
        }else {
            return -1;
        }
    }
    // 判断一棵树是否为对称树
    public boolean isSymmetric(TreeNode root) {
        if(root==null)
            return true;
        return isSymmetricChild(root.left,root.right);
    }
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){
        if(leftTree==null&&rightTree!=null||leftTree!=null&&rightTree==null){
            return false;
        }
        if(leftTree == null&&rightTree==null){
            return true;
        }
        if(leftTree.val != rightTree.val){
            return false;
        }
        return isSymmetricChild(leftTree.left,rightTree.right)
                &&isSymmetricChild(leftTree.right,rightTree.left);
    }

}
